A content addressable memory (CAM) device is a storage device that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, are searched in parallel for a match with the comparand data. If a match exists, the CAM device indicates the match by asserting a match flag. Multiple matches may also be indicated by asserting a multiple match flag. The CAM device typically includes a priority encoder to translate the matched location into a match address or CAM index and outputs this address to a status register. The match address, the contents of the matched location, and other status information (e.g., skip bit, empty bit, full flag, as well as, match and multiple match flags) may be output from the CAM device to an output bus.
CAM devices may be depth cascaded together to form a larger CAM device or system. For example, two 1 k .times.64 CAM devices may be depth cascaded together to form a 2 k.times.64 CAM. Depth cascading may be implemented using match flag input and output pins. A higher priority CAM device (i.e., the CAM device with a lower physical addresses) may have its match flag output pin connected to the match flag input pin of the lower priority CAM device (i.e. the CAM device with the higher physical addresses). In response to a compare instruction, each CAM device simultaneously compares compared data with data stored in its respective CAM array. If the higher priority CAM device has a match, it will notify this result to the lower priority CAM device by asserting its match flag output signal. The higher priority CAM device may then output its match address to a common output bus, and the lower priority CAM device will be disabled from outputting data to the common output bus. If, however, the higher priority CAM device does not have a match, it will not assert its match flag output and the lower priority CAM device may provide its match address to the common output data bus (if it has a match). If there are many CAM devices depth cascaded together, then the lowest priority CAM device in the cascade will only be able to output its data to the common output bus if no other CAM devices in the cascade have a match. That is, the lowest priority CAM device will have to wait until the match flag signals from the previous CAM devices have rippled through the depth cascade chain. This may result in undesirably long response times for the depth cascaded CAM system to respond to a compare instruction.
It may not be desirable to use only the match flag input and output pins when depth cascading CAM devices that operate in a flow-through mode. CAM devices that operate in a flow-through mode may be able to output a match address, data from a matched location in a CAM array, and other status information (e.g., match flag, multiple match flag, full flag, skip bit, empty bit, or a device identification) in a single clock cycle. For example, a higher priority CAM device that does not have a match will not assert its match flag during the single clock cycle. A lower priority CAM with a match will not know if it can output its match address to the common output data bus during the clock cycle because it does not know whether the higher priority CAM device has a slow response time, or whether the higher prioirty CAM device does not have a match.
One possible solution may be to allow each of the CAM devices in the cascade to output its match address to the common output data bus and then allow each CAM device to be disabled appropriately when the match flag results ripple through the cascade. This solution, however, may result in a number of disadvantages, including: (1) causing bus contention problems, (2) causing an undesirable amount of power to be drawn by the system as potentially all CAM devices may be driving the common output data bus at the same time, and (3) slowing down the system as capacitance may be increased on the common output data bus.
Therefore, what is needed is a mechanism for depth cascading CAM devices that operate in a flow-through mode.